L2-014 列车调度

题目 L2-014 列车调度

思路分析

是拦截导弹的简化

代码实现

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
using ull = unsigned long long;
using PII = pair<int,int>;
using Pll = pair<ll,ll>;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
const int inf = 0x3f3f3f3f;

const int N=1e5+10;
int stackTop[N],cnt;

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	int n,x;cin>>n;

	while(n--){
		cin>>x;

		int l=0,r=cnt;
		while(l<r){ //----- |-----
			int mid=l+r>>1;
			if(stackTop[mid]>=x)
				r=mid;
			else
				l=mid+1;
		}
		if(stackTop[r]<x)	r++;
		cnt=max(cnt,r);
		stackTop[r]=x;
	}
	cout<<cnt;
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
using ull = unsigned long long;
using PII = pair<int,int>;
using Pll = pair<ll,ll>;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
const int inf = 0x3f3f3f3f;

const int N=1e5+10;
set<int> stackTop;

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	int n,x;cin>>n;

	while(n--){
		cin>>x;

		auto i = stackTop.lower_bound(x);
		if(i!=stackTop.end()){
			stackTop.erase(i);
			stackTop.insert(x);
		}else{
			stackTop.insert(x);
		}
	}
	cout<<stackTop.size();
	return 0;
}

同类题型

视频讲解

⬅️ L2-013 红色警报 🏠 00-天梯赛 ➡️ L2-015 互评成绩